package com.wmx.datastructuresandalgorithms.sortalgorithm.search;

import java.util.Arrays;

/**********************************
 * @author wmx
 * @date 2019/9/4 16:41
 * @description:
 * @version 1.0
 *
 * 插值查找 ：
 * 使用于有序的数组。
 * 分散比较均匀的数据会比较快。分散不均匀的数据查询的时候未必比二分法查找快。
 *
 * 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.
 * 关键字分布不均匀的情况下，该方法不一定比折半查找要好
 ************************************/
public class InsertSearch {

    public static void main(String[] args) {
        /*int [] arr = new int[100];
        for (int i = 0; i < 100 ; i++) {
            arr[i] = i ;
        }*/
        int [] arr = {1,20,800,9000,80000,88000,1000000,2000000};
        int i = insertSearch(arr, 0, arr.length - 1, 200000);
        System.out.println(i);


    }
    public static int  insertSearch(int [] arr ,int let ,int right ,int value){
        System.out.println("查询了次数");
        //注意:value < arr[0] 和 value > arr[right] 必须需要

        if(let > right || value  < arr[let] || value > arr[right] ){
            return -1;
        }

         int min = let + (right - let) * (value - arr[let])/(arr[right] - arr[let]);

        if(arr[min] > value){
            return  insertSearch(arr,let,min-1,value);
        }else if (arr[min] < value){
            return  insertSearch(arr , min+1 ,right,value);
        }else {
            return  min;
        }

    }
}
